package com.le.medium.class4;

import org.junit.Test;

/**
 * 给定一个数组arr长度为N，
 * 你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。
 * 但是每种划分下都有左部分的最大值和右部分的最大值，
 * 请返回最大的， 左部分最大值减去右部分最大值的绝对值。
 */
public class Problem06_MaxABSBetweenLeftAndRight {

    // 生成从左到右的最大值数组
    // 生成从右往左的最大值数组
    // 从1...n-2方位内依次比较 获得结果
    public static int maxABS1(int[] arr) {
        int[] leftMax = new int[arr.length];
        leftMax[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            leftMax[i] = Math.max(arr[i], leftMax[i - 1]);
        }
        int[] rightMax = new int[arr.length];
        rightMax[arr.length - 1] = arr[arr.length - 1];
        for (int i = arr.length - 2; i > -1; i--) {
            rightMax[i] = Math.max(arr[i], rightMax[i + 1]);
        }
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length - 1; i++) {
            res = Math.max(res, Math.abs(leftMax[i - 1] - rightMax[i + 1]));
        }
        return res;
    }

    // 寻找全局最大值
    public static int maxABS2(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        return max - Math.min(arr[0], arr[arr.length - 1]);
    }

    public static int[] generateRandomArray(int length) {
        int[] arr = new int[length];
        for (int i = 0; i != arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000) - 499;
        }
        return arr;
    }

    @Test
    public void test(){
        int[] arr = generateRandomArray(200);
        System.out.println(maxABS1(arr));
        System.out.println(maxABS2(arr));
    }
}
